package com.xieyong.leetcode;

import java.util.Stack;

public class Leetcode962 {

    public static void main(String[] args) {
        Leetcode962 leetcode = new Leetcode962();
        int[] nums = {9,8,1,0,1,9,4,0,4,1};
        int i = leetcode.maxWidthRamp(nums);
        System.out.println(i);
    }
//          下面这个方法超时了
//    public int maxWidthRamp(int[] nums) {
//        int max = 0;
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = nums.length - 1; j > i; j--) {
//                if(nums[j] >= nums[i]) {
//                    max = Math.max(max, j - i);
//                    break;
//                }
//            }
//        }
//        return max;
//    }
    public int maxWidthRamp(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
//        维护一个单调递减栈，遍历一遍数组构建单调递减的单调栈，存储每一个元素下标
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] < nums[stack.peek()]) {  // 这里不使用等号可以减少栈中存储的元素
                stack.push(i);
            }
        }
        int max = 0;
//        从后往前循环，判断是否大于栈顶元素，依次计算长度
        for (int i = nums.length - 1; i >= 0; i--) {
            while(!stack.isEmpty() && nums[stack.peek()] <= nums[i]) { // 题目中使用等号
                max = Math.max(max, i - stack.pop());
            }
        }
        return max;
    }
}

